class ListNode4 {
    int val;
    ListNode4 next;

    ListNode4() {
    }

    ListNode4(int val) {
        this.val = val;
    }

    ListNode4(int val, ListNode4 next) {
        this.val = val;
        this.next = next;
    }

}


public class Java1020 {
    ListNode4 head;
    public void show() {
        ListNode4 x = head;

        while (x != null){
            System.out.print(x.val+" ");
            x = x.next;
        }
    }

    //重载一个show方法
    public void show(ListNode4 partition) {
        ListNode4 x = partition;

        while (x != null){
            System.out.print(x.val+" ");
            x = x.next;
        }
    }

    public int size(){
        ListNode4 x = head;
        int count = 0;
        while (x != null){
            count++;
            x = x.next;
        }

        return count;
    }

    public void addLast(int key){
        ListNode4 node = new ListNode4(key);
        if(size() == 0)
        {
            head = node;
            return;
        }

        ListNode4 x = head;
        while (x.next != null){
            x = x.next;
        }
        x.next = node;
    }


    public ListNode4 partition(int x) {
        ListNode4 bs = null;
        ListNode4 be = null;
        ListNode4 as = null;
        ListNode4 ae = null;

        ListNode4 cur = head;
        while (cur != null) {
            if (cur.val < x) {

                //在这个段中第一次插入数据
                if (bs == null) {
                    bs = be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            }

        else {
            //在这个段中第一次插入数据
            if (as == null) {
                as = ae = cur;
            } else {
                ae.next = cur;
                ae = ae.next;
            }

        }
            cur = cur.next;
        }

        //假如没有<x的1数据
        if(bs == null){
            return as;
        }
        be.next = as;
        //将最后一个结点置为空
        if(as != null){
            ae.next = null;
        }
       return bs;
    }

    public static void main(String[] args) {
        Java1020 x = new Java1020();
        x.addLast(11);
        x.addLast(14);
        x.addLast(18);
        x.addLast(77);
        x.addLast(12);


        x.show();
        ListNode4 y = x.partition(60);
        System.out.println();
        x.show(y);
    }


}